Let S be a set of imprecise points that is represented by axis-aligned pairwise disjoint squares in the plane. A precise instance of S is a set of points, one from each region of S. In this paper, we study the optimal Minimum Spanning Tree (OptMST) problem on S. The OptMST problem looks for the precise instance of S such that the weight of the MST in this instance, maximize (Max-MST) or minimize (Min-MST) between all precise instances of S under L1-metric. We present a ( 3 7)-approximation algorithm for Max-MST. This is an improvement on the best-known approximation factor of 1=3. If S satis es k-separability property (the distance between any pair of squares are at least k: amax where amax is the maximum length of the squares), the factor parameterizes to 2k+3 2k+7. We propose a new lower bound for Min-MST problem on S under L1-metric where S contains unit squares and provide an approximation algorithm with (1 + 2p2) asymptotic factor.

Capacitated Minimum Spanning Tree Problem (CMSTP), a well-known combinatorial optimization problem, holds the central place in telecommunication network design. This problem involves  nding a Minimum cost Spanning Tree with an extra cardinality limitation on the orders of the subTrees incident to a certain root node. The Balanced Capacitated Minimum Spanning Tree Problem (BCMSTP) is a special case that aims to balance the orders of the subTrees. This problem is an NP-hard one and presents two approximation algorithms in this paper. By considering the maximum order of the subTrees Q, a (3 􀀀 1Q )-approximation algorithm was provided to  nd a balanced solution. This result was improved to a (2: 5 +  ) approximation algorithm (for every given  > 0) in the 2d-Euclidean spaces. Also, a Polynomial Time Approximation Scheme (PTAS) was presented for CMSTP.

There have been several efforts in the literature to extract as much information as possible from the financial networks. Most of the research has been concerned about the hierarchical structures, clustering, topology and also the behavior of the market network; but not a notable work on the network filtration exists. This paper proposes a stock market filtering model using the correlation - based financial networks in which network nodes represent the potential stocks and network edges indicate the correlation coefficients of corresponding stock pairs. The model is capable of reducing the basic market size while keeping the diversification and risk - return expectations fairly constant. The novelty of this research is to develop a new market network filtering method which exploits Minimum Spanning Tree (MST) to reduce the number of network nodes (graph order) rather than the links (graph size). The proposed method chooses the nodes (stocks) based on dangling ends of the constructed MST. In order to verify our proposed model, we applied the model on data of three stock markets: New York Stock Exchange (NYSE), Germany Stock Exchange (DAX) and Toronto Stock Exchange (TSE). In conclusion, the numerical results showed that our proposed model can make a subset of the stock market in which its performance can imitate the whole market with a rather considerable reduction in size; as a result, we can have a diversified subset of the market compatible with that of the whole market. The performance of the model is confirmed by comparing the portfolio of the filtered market network with the whole market portfolio using the complement of Herfindahl Index as a measure of diversification.

Nowadays, financial markets in Iran have attracted the attention of many managers, investors and financial policymakers. Therefore, in order to make the optimal decision and reduce the risks in such a market, it is important to identify and analyze the network behavior of the financial markets at different times to obtain the optimal decision. The current study aims to answer the following research question; how is it possible to use the Minimum Spanning Tree and hierarchical clustering in the network analysis of the Tehran Stock Exchange? The period examined was 2013 to 2018. The population consisted of all the companies accepted in Tehran Stock Exchange. The sampling was selected purposefully and contained the companies which had at least one trading day in the time span from the beginning of 2013 to the end of 2018. The stock of the investigated companies was considered as the vertexes of one graph and the coherent information criterion was considered as the weight of the edge. First, the Minimum Spanning Tree of the graph was calculated. The results revealed that the stocks of DarooAbuReihan, DarooPakhsh and Alborzdaroo had a high influence on directing the prices of the other stocks. Furthermore, the results of hierarchical clustering classified the stocks of the companies into 8 clusters. This study presents a viewpoint about the modern method designed for the analysis of complex financial networks. Moreover, the study offers an analysis of Iran's stock market structure which can be the center of finance researchers and analysts' attention.

Due to the many applications of the travelling salesman problem, solving this problem has been considered by many researchers. One of the subsets of the travelling salesman problem is the metric travelling salesman problem in which a triangular inequality is observed. This is a crucial problem in combinatorial optimization as it is used as a standard problem as a basis for proving complexity or providing solutions to other problems in this class. The solution is used usually in logistics, manufacturing and other areas for cost minimization. Since this is an NP-hard problem, heuristic and meta-heuristic algorithms seek near-optimal solutions in polynomial time as numerical solutions. For this purpose, in this paper, a heuristic algorithm based on the Minimum Spanning Tree is presented to solve this problem. Then, by generating 20 instances, the efficiency of the proposed algorithm was compared with one of the most famous algorithms for solving the travelling salesman problem, namely the nearest neighbour algorithm and the ant colony optimization algorithm. The results show that the proposed algorithm has good convergence to the optimal solution. In general, the proposed algorithm has a balance between runtime and the solution found compared to the other two algorithms. So the nearest neighbour algorithm has a very good runtime to reach the solution but did not have the necessary convergence to the optimal solution, and vice versa, the ant colony algorithm converges very well to the optimal solution, but, its runtime solution is very longer than the proposed algorithm.